1. Field of the Invention
The present invention generally relates to the field of cryptography, particularly to cryptographic methods and devices and, even more particularly, to methods for preventing security attacks to cryptosystems based on information leakage.
2. Description of the Related Art
The past approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not to be considered prior art to the claims in this application merely due to the presence of these approaches in this background section.
In modem data communication systems, a wide use of cryptographic techniques providing confidentiality and authenticity of information was enabled by the invention (by W. Diffie and M. Hellman in 1976) of so-called “public-key cryptosystems”, which provide efficient solutions to the inherent secret-key management problem.
In particular, public-key cryptosystems are mostly used for Diffie-Hellman key exchange, for digital signatures, and for encrypting secret session keys to be used in secret-key cryptosystems. For example, they are used in the Internet protocols including Secure Socket Layer (SSL), Internet Protocol Security (IPSec), and Pretty Good Privacy (PGP).
Elliptic Curve Cryptosystems (ECCs), proposed independently by V. S. Miller in 1985 and N. Koblitz in 1987, are evolving as an efficient alternative to classical public-key cryptosystems, such as Diffie-Hellman key exchange based on finite field multiplicative groups and RSA, invented by R. L. Rivest, A. Shamir, and L. Adleman in 1978, by offering the same security level for much smaller key sizes, thus allowing for more efficient implementations both in hardware and software.
Typical ECCs include cryptographic protocols such as Elliptic Curve Diffie-Hellman (ECDH), used for secret key exchange, and Elliptic Curve Digital Signature Algorithm (ECDSA), adopted as international standard ANSI X9.62, used for digital signatures. These protocols are also covered by the IEEE 1363 series of standards.
ECCs are based on mathematical entities called “elliptic curve groups”. An elliptic curve group is defined as an Elliptic Curve (EC), which is a set of solutions, called “points”, to an elliptic curve equation, together with an appropriately defined operation among the points on the curve.
The basic two types of ECs are defined over the fields containing a prime number of elements and over the fields with a number of elements being an integer power of 2. The former are also called “prime fields” or “integer fields” or “fields of a prime characteristic”, their elements are integers, and operations of addition and multiplication are defined modulo a prime number. The latter are also called “binary polynomial fields” or “fields of characteristic 2”, their elements are binary polynomials, and operations of addition and multiplication are defined as addition and multiplication of polynomials modulo an irreducible polynomial, respectively.
A binary polynomial field F2m, i.e., a finite field of characteristic 2, is a finite field with 2m elements, where m is a positive integer, which represents the dimension or the bit size of the field F2m. It is composed of a set of polynomials over the binary field F2 whose degree is at most m−1, together with the operations of addition and multiplication defined as addition and multiplication of polynomials modulo an irreducible polynomial of degree m over F2, respectively. By irreducible polynomial over F2 there is meant a polynomial that cannot be written as a product of two polynomials over F2 having degrees of at least 1. In other words, the elements of the field F2m, are binary polynomials of degree less than m, and, given an irreducible polynomial f(z) of degree m, called “reduction polynomial”, the sum of two elements a(z) and b(z), also denoted as a+b, is defined as (a(z)+b(z)) mod f(z)=a(z)+b(z), that is, the coefficients are simply bitwise added, which is an operation also denoted as a a⊕b, and the product of the two elements a(z) and b(z), also denoted as a·b, is defined as (a(z)·b(z)) mod f(z), that is, as the remainder obtained after dividing the product a(z)·b(z) by f (z).
The binary addition, i.e., the addition in F2, is the same as an addition modulo 2 or a logic XOR operation, whereas the binary multiplication, i.e., the multiplication in F2, is the same as a logic AND operation. For the purposes of the present description, a polynomial of degree less than m is defined as a vector of m coefficients, a(z)=am-1zm-1+am-2zm-2+ . . . +a1z+a0=a=(am-1, am-2, . . . , a1, a0), whereas the sum and the product of polynomials are defined as usual. As an alternative to this representation, called the “polynomial basis” representation, other representations can also be used, such as the so-called “normal basis” representation.
According to the Weierstrass equation, an elliptic curve E(F2m): y2+xy=x3+ax2+b over the field F2m, specified by the parameters a,bεF2m such that b≠0, is defined as the set of points P=(x,y), x,yεF2m, being the solutions to the equation:y2+xy=x3+ax2+b, together with a special, neutral point O, also called “point at infinity”. The couple (x,y) represents the x-coordinate and the y-coordinate of a generic point P on an elliptic curve.
An elliptic curve forms a group with respect to the operation of addition that is defined as follows.    Neutral point: P+O=O+P=P for all P=(x,y)εE(F2m).    Negative point: If P=(x,y)εE(F2m), then (x,y)+(x,x⊕y)=O, and the point (x,x⊕y)ε(F2m) is denoted as −P and called the negative of the point P.    Addition of points: Let P=(x1,y1)εE(F2m) and Q=(x2,y2)εE(F2m), where P≠±Q. Then P+Q=(x3,y3), where
            x      3        =                  λ        2            +      λ      +              x        1            +              x        2            +      a        ,            y      3        =                  λ        ⁡                  (                                    x              1                        +                          x              3                                )                    +              x        3            +              y        1              ,      λ    =                                        y            2                    +                      y            1                                                x            2                    +                      x            1                              .          Doubling of a point: Let P=(x1,y1)εE(F2m), where P≠O. Then P+P=2P=(x3,y3), where
            x      3        =                  λ        2            +      λ      +      a        ,            y      3        =                  λ        ⁡                  (                                    x              1                        +                          x              3                                )                    +              x        3            +              y        1              ,      λ    =                  x        1            +                                    y            1                                x            1                          .            
It can be appreciated that the expressions for the point doubling operation are the same as those for the point addition, due to fact that x1+x1=0, except for the value of λ, which is different. Consequently, both the addition and the doubling of points can be performed as sequences of multiplications, squaring operations, additions, and inversions in F2m.
To avoid computing the inversion, which is typically a more complex operation than computing the other operations in the field F2m, an elliptic curve point can be represented by the so-called “projective coordinates”, instead of the classical, affine coordinates. The corresponding expressions do not include the inversion, but the number of multiplications is increased.
The main operation over elliptic curve groups that is required for cryptosystems such as ECDH or ECDSA is a repeated addition of a generic point P with itself k−1 times, P+ . . . +P, an operation called the “scalar multiplication” of a base point P by a scalar k and is denoted as kP, where k is a positive integer. In practical applications, k is a secret and very big number, typically, several hundred bits long.
It is known in the art that the scalar multiplication can be computed efficiently by using an algorithm called “double-and-add”, in the left-to-right (i.e., going from the most significant bit of k downwards) or right-to-left (from the least significant bit of k upwards) manner, where
  k  =                    (                              k                          t              -              1                                ,                      k                          t              -              2                                ,          …          ⁢                                          ,                      k            1                    ,                      k            0                          )            2        =                  ∑                  i          =          0                          t          -          1                    ⁢                        k          i                ⁢                              2            i                    .                    The algorithm consists of a series of point doublings and point additions, where the positions of point additions depend on the scalar k. More precisely, the algorithm consists of t iterations, each iteration consisting of a point doubling that is followed by a point addition only if the corresponding scalar bit is equal to 1.
It is known in the art that if a cryptographic algorithm, such as, for example an ECC, is implemented on a microelectronic device, e.g., an integrated circuit chip card, then even for tamper-resistant chips, where the underlying integrated circuit is protected by special physical measures, such as protective layers and various sensors and detectors, the sensitive information, which is dependent on the underlying secret or private key, may leak out through various side channels while being processed during the execution of the cryptographic algorithm. For example, the sensitive information may leak out through measurements of the timing, power consumption, and electromagnetic radiation, as well as monitoring of signals by micro-probing. The objective of these “side-channel” attacks is to recover the secret key by using the information leaking out from said side channels.
In particular, the timing attacks were introduced by P. Kocher, in “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,” Advances in Cryptology—Crypto '96, Lecture Notes in Computer Science, vol. 1109, pp. 104-113, 1996; the power analysis attacks were introduced by P. Kocher, J. Jaffe, and B. Jun, in “Differential power analysis,” Advances in Cryptology—Crypto '99, Lecture Notes in Computer Science, vol. 1666, pp. 388-397, 1999.
The two basic power analysis attacks are referred to as “Simple Power Analysis” (SPA) attacks and “Differential Power Analysis” (DPA) attacks. An SPA attack utilizes a single power consumption curve and tries to deduce information about the secret key from this curve, whereas a DPA attack utilizes a set of power consumption curves, guesses a part of the secret key, and then verifies if the guess is correct by a simple processing of the curves according to the corresponding guess. The timing attacks can utilize single or multiple measurements.
The timing and power analysis attacks do not require expensive resources, and most implementations, without specific countermeasures incorporated therein, are vulnerable to them. Therefore, there is a need to protect the sensitive data from side-channel attacks by appropriate changes in the cryptographic algorithm, of course, without changing the overall functionality of the algorithm.
A problem with a direct implementation of the double-and-add algorithm for performing the scalar multiplication is that the computations required for the point addition and the point doubling in general are different. As a consequence, the timing, as well as the power consumption of a hardware device implementing the cryptographic algorithm may depend on the secret scalar k. Thus, the double-and-add algorithm is potentially vulnerable to the timing attack and SPA attack: by analyzing the timing and/or the power consumption curve it may be possible to identify the iterations where the point addition is effectively performed, that is, when the scalar bit is equal to 1, and thus reconstruct the secret scalar.
For elliptic curves over binary polynomial fields, the computations required for the point addition and point doubling are not the same, the difference mainly coming from the computation of the variable λ. Accordingly, in affine coordinates, the difference in the computation only relates to the total number of field additions, and not to the total number of field inversions, multiplications, or squaring operations (shortly, squarings), which are computationally more complex. However, the timing and power consumption associated with the inversion, which is the computationally most expensive operation, significantly depend on the operand being inverted, and this may be a source of information leakage. On the other hand, in projective coordinates, the difference also relates to the field operations of multiplication and squaring.
One known way of dealing with the problem of unbalanced computations, especially in projective coordinates, is to modify the basic double-and-add algorithm by introducing a dummy point addition whenever the corresponding scalar bit is equal to 0, which results in the so-called “double-and-add-always” algorithm, or, possibly, to perform other algorithms, as sequences of point doublings, additions, and subtractions, which differ from the double-and-add algorithm in that they have a more balanced timing and power consumption. Typically, the modified algorithms or new algorithms require a considerable increase of the total time needed, but the point addition and point doubling need not be indistinguishable. The following documents describe algorithms of this type.
EP 1,160,661 A describes several algorithms for scalar multiplication of the double-and-add-always type including those where the order or point additions and doublings is randomized, the proposed algorithms being especially suitable for elliptic curves in the so-called Montgomery form.
U.S. Pat. No. 6,738,478 B1 proposes a variant of the Montgomery ladder algorithm for scalar multiplication that is claimed to provide resistance to timing and SPA attacks, for elliptic curves over binary polynomial or prime fields.
US 2003/0123656 A1 discloses two scalar multiplication algorithms of the double-and-add-always type in which the point addition and doubling can be performed simultaneously at the expense of introducing some auxiliary variables. In addition, a number of techniques for the point addition and doubling are also proposed, and they relate to elliptic curves over arbitrary finite fields.
Another known method, suggested by E. Trichina and A. Bellezza in “Implementation of elliptic curve cryptography with built-in counter measures against side channel attacks,” Cryptographic Hardware and Embedded Systems—CHES 2002, Lecture Notes in Computer Science, vol. 2523, pp. 98-113, 2002, aims at balancing the computations required for the point addition and point doubling themselves. The method involves the use of projective Jacobian coordinates, and consists in splitting the point addition in two parts, and in representing the point doubling and each part of the point addition by the same sequence of field operations (with different operands), by introducing some dummy elementary operations and by an appropriate reordering of the elementary operations. This makes it difficult to identify the iteration steps when the scalar bit equals 1, in scalar multiplication algorithms such as the double-and-add algorithm.
US 2005/0163312 A1 proposes another method for balancing the computations for the point addition and point doubling. The method uses affine coordinates and consists in representing the point addition and point doubling by the same sequence of field operations (with different operands), by introducing some dummy field additions and by an appropriate reordering of the elementary operations. The sequence of operations includes one field division, one field squaring, and a number of field multiplications and additions.
J. C. Yoon, S. W. Jung, and S. Lee in “Architecture for an elliptic curve scalar multiplication resistant to some side-channel attacks,” Information Security and Cryptography—ICISC 2003, Lecture Notes in Computer Science, vol. 2971, pp. 139-151, 2003, propose a sort of double-and-add always algorithm for scalar multiplication for elliptic curves over binary polynomial fields in affine coordinates, in which some operations of point addition and point doubling are parallelized, thus achieving a better performance. Also, a randomized version of the Montgomery inverse algorithm for the inversion operation is proposed, providing some resistance to timing attacks as well as SPA and DPA attacks.
Yet another known method is to randomize the scalar multiplication algorithm by randomizing the elliptic curve in question, the base point, the coordinates, and/or the secret scalar itself, without changing the final result. This also helps counteract the DPA attack, in addition to the timing attack and SPA attack.
In particular, it is suggested by P. Kocher, in “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,” Advances in Cryptology—Crypto '96, Lecture Notes in Computer Science, vol. 1109, pp. 104-113, 1996, to randomize the scalar by adding thereto a random integer multiple of the base point order, n, in view of the fact that kP=kP+rnP=(k+rn)P. More precisely, this was suggested by using the multiplicative instead of additive terminology for a group operation, in which the exponentiation is an analog of the scalar multiplication.
J.-S. Coron explicitly suggested in “Resistance against differential power analysis for elliptic curve cryptosystems,” Cryptographic Hardware and Embedded Systems—CHES '99, Lecture Notes in Computer Science, vol. 1717, pp. 292-302, 1999, that a 20-bit random number r may be sufficient, but it was later shown by P.-A. Fouque and F. Valette, in “The doubling attack—Why upwards is better than downwards,” Cryptographic Hardware and Embedded Systems—CHES 2003, Lecture Notes in Computer Science, vol. 2779, pp. 269-280, 2003, that under some conditions this is not sufficiently secure, especially if the bit size of r is relatively small and if one can distinguish the point addition from the point doubling.
Another technique for randomizing the scalar consists in splitting the scalar in two random parts by using the integer addition modulo n, according to k=k1+k2 mod n, and then to compute kP=k1P+k2P. An example of such a technique combined with the representation of points in the projective Jacobian coordinates is provided in EP 1,217,783 A1.
In U.S. Pat. No. 6,252,959 B1, the radix representation of the scalar in base of the form 2k in a scalar multiplication algorithm is used, in order to reduce the total number of field inversions required, for elliptic curves over binary polynomial fields.
U.S. Pat. No. 6,141,420 describes a set of techniques for scalar multiplication and underlying field operations for elliptic curves over binary polynomial fields by using the normal basis representation. Emphasis is put on efficient computation rather than resistance to side-channel attacks.